/*
 * p2154.cpp
 *
 *  Created on: 2013-3-9
 *      Author: zy
 */

#include<cstdio>
#include<cstring>
#include <algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#define LL long long
using namespace std;

int N,P,L;
const int TIME = 11;
LL factor[1000000],ans;
int fac_top,a[1000000];
LL Abs(LL n)
{
	if (n < 0)
		return -n;
	return n;
}
LL gcd(LL small, LL big)
{
	while (small)
	{
		swap(small, big);
		small %= big;
	}
	return Abs(big);
}
int phi(int n)
{
	int rea=n;
	for(int i=1;i<=fac_top;i++)
		if(n%factor[i]==0)
		{
			rea=rea-rea/factor[i];
			do
				n/=factor[i];
			while(n%factor[i]==0);
		}
	if(n>1)rea=rea-rea/n;
	return rea;
}

LL muti_mod(LL a, LL b, LL n)
{
	LL exp = a % n, res = 0;
	while (b)
	{
		if (b & 1)
		{
			res += exp;
			if (res > n)
				res -= n;
		}
		exp <<= 1;
		if (exp > n)
			exp -= n;
		b >>= 1;
	}
	return res;
}
// ret = (a^b)%n
LL mod_exp(LL a, LL p, LL m)
{
	LL exp = a % m, res = 1; //
	while (p > 1)
	{
		if (p & 1) //
			res = muti_mod(res, exp, m);
		exp = muti_mod(exp, exp, m);
		p >>= 1;
	}
	return muti_mod(res, exp, m);
}

bool miller_rabin(LL n, int times)
{
	if (n == 2)
		return 1;
	if (n < 2 || !(n & 1))
		return 0;
	LL a, u = n - 1, x, y;
	int t = 0;
	while (u % 2 == 0)
	{
		t++;
		u /= 2;
	}
	srand(time(0));
	for (int i = 0; i < times; i++)
	{
		a = rand() % (n - 1) + 1;
		x = mod_exp(a, u, n);
		for (int j = 0; j < t; j++)
		{
			y = muti_mod(x, x, n);
			if (y == 1 && x != 1 && x != n - 1)
				return false; //must not
			x = y;
		}
		if (y != 1)
			return false;
	}
	return true;
}
LL pollard_rho(LL n, int c)
{
	LL x, y, d, i = 1, k = 2;
	srand(time(0));
	x = rand() % (n - 1) + 1;
	y = x;
	while (true)
	{
		i++;
		x = (muti_mod(x, x, n) + c) % n;
		d = gcd(y - x, n);
		if (1 < d && d < n)
			return d;
		if (y == x)
			return n;
		if (i == k)
		{
			y = x;
			k <<= 1;
		}
	}
}
void findFactor(LL n, int k)
{
	if (n == 1)
		return;
	if (miller_rabin(n, TIME))
	{
		factor[++fac_top] = n;
		return;
	}
	LL p = n;
	while (p >= n)
		p = pollard_rho(p, k--);
	findFactor(p, k);
	findFactor(n / p, k);
}
void dfs(int k,int top)
{
	if(k>top)
	{
		int k=N/L-1;
		int t=phi(L);
		LL tem= mod_exp((LL)N,(LL)k,(LL)P);
		if(k==0)tem=1%P;
		ans=(ans+muti_mod((LL)t,tem,(LL)P))%P;
		return;
	}
	for(int i=0;i<=a[k];i++)
	{
		int tem=(int)(pow(factor[k]+0.0,i));
		L=L*tem;
		dfs(k+1,top);
		L=L/tem;
	}
}
int main()
{
	int X;
	scanf("%d",&X);
	while(X--)
	{
		ans=0;
		scanf("%d%d",&N,&P);
		if (N == 1){printf("%d\n",1%P);continue;}
		fac_top = 0;
		findFactor(N, 107);
		sort(factor + 1, factor + 1 + fac_top);
		int c = fac_top;
		fac_top = 0;
		for (int i = 1; i <= c;)
		{
			LL current = factor[i];
			factor[++fac_top] = current;
			for (; i <= c && current == factor[i]; i++)
				;
		}
		for(int i=1;i<=fac_top;i++)
		{
			int t=N;
			a[i]=0;
			while(t%factor[i]==0)
			{
				a[i]++;
				t=t/factor[i];
			}
		}
		L=1;
		dfs(1,fac_top);
		printf("%lld\n",ans);
	}
	return 0;
}
